#include "Dijkstra.h"


Dijkstra::Dijkstra()
{
	this->listener = 0;
	this->graph = 0;
	this->source = -1;
}


Dijkstra::~Dijkstra()
{
}


bool Dijkstra::CalculateShortestDistances(IncidenceGraph* graph, int source)
{
	if (!graph->ContainsVertex(source))
		return false;
	if (graph->EdgeCount() == 0)
		return true;

	// save for later
	this->graph = graph;
	this->source = source;

	// initialize a map of shortest paths from source vertex, and a list
	// of unvisited vertices
	shortestPaths.clear();
	auto vertices = graph->GetVertices();
	auto unvisited = map<int, bool>();
	for (auto it = vertices.begin(); it != vertices.end(); it++) {
		shortestPaths[it->i] = PathVertex(it->i, -1, INFINITY);
		unvisited[it->i] = true;
	}

	// set source vertexes cost to zero
	shortestPaths[source].distance = 0;

	// visit all vertices in the graph
	int iteration = 0;
	for (auto it = vertices.begin(); it != vertices.end(); it++) {
		if (listener) {
			listener(iteration, NEXT_ITERATION,
					 &shortestPaths, &unvisited,
					 -1, 0, -1, 0, 0, 0);
		}

		// select an unvisited node with the shortest distances and remove
		// it from the list of unvisited nodes
		auto current = -1;
		auto distance = INFINITY;
		for (auto itt = unvisited.begin(); itt != unvisited.end(); itt++) {
			auto vertex = shortestPaths[itt->first];
			if (vertex.distance < distance) {
				distance = vertex.distance;
				current = itt->first;
			}
		}
		unvisited.erase(current);

		// were done if there are no unvisited nodes left
		if (unvisited.empty()) {
			if (listener) {
				listener(iteration, LAST_ITERATION,
						 &shortestPaths, &unvisited,
						 current, 0, -1, distance, 0, 0);
			}
			break;
		}

		if (listener) {
			listener(iteration, FIND_SHORTEST_UNVISITED,
					 &shortestPaths, &unvisited,
					 current, 0, -1, distance, 0, 0);
		}

		// visit each neighbor and update shortest distances
		auto neighbors = graph->GetEdges(current);
		if (listener) {
			listener(iteration, VISIT_CONNECTED_EDGES,
						&shortestPaths, &unvisited,
						current, neighbors.size(), -1, distance, 0, 0);
		}
		for (auto itt = neighbors.begin(); itt != neighbors.end(); itt++) {
			auto vertex = shortestPaths[itt->j];
			auto newDistance = distance + itt->weight;
			auto oldDistance = vertex.distance;
			if (newDistance < vertex.distance) {
				vertex.distance = newDistance;
				vertex.previous = current;
				shortestPaths[itt->j] = vertex;
				if (listener) {
					listener(iteration, UPDATE_DISTANCE,
							 &shortestPaths, &unvisited,
							 current, neighbors.size(), itt->j, distance, oldDistance, newDistance);
				}
			}
		}

		// increment iteration count for listener
		iteration++;
	}

	return true;
}


list<PathVertex> Dijkstra::GetShortestPath(int target)
{
	auto path = list<PathVertex>();
	auto current = shortestPaths[target];

	// iterate backwards, starting from the target vertex
	path.push_front(current);
	while (current.previous > -1) {
		current = shortestPaths[current.previous];
		path.push_front(current);
	}

	// check that we reached the start vertex
	if (current.current != source)
		path.clear();

	return path;
}


double Dijkstra::GetDistance(int target)
{
	return shortestPaths[target].distance;
}


list<PathVertex> Dijkstra::GetDistances()
{
	auto l = list<PathVertex>();
	for (auto it = shortestPaths.begin(); it != shortestPaths.end(); it++) {
		l.push_back(it->second);
	}
	return l;
}


int Dijkstra::GetPathCount()
{
	int n = 0;
	for (auto it = shortestPaths.begin(); it != shortestPaths.end(); it++) {
		if (it->second.distance < INFINITY)
			n++;
	}
	return n;
}